package 中等.搜索.回溯;

/**
 * 给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
 * 如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，
 * 则认为该子数组是一个 美丽 子集。
 * 返回数组 nums 中 非空 且 美丽 的子集数目。
 * nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）
 * 得到的一个数组。只有在删除元素时选择的索引不同的情况下，
 * 两个子集才会被视作是不同的子集。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/the-number-of-beautiful-subsets
 */
public class 美丽子集的数目_6352 {

    public static void main(String[] args) {

    }

    /**
     * 回溯
     * 回溯搜索每一种情况，每个位置可以选或者不选，当
     * 之前已经选过 nums[i]+k 或者 nums[i]-k 的数子，
     * 那么当前一定不能选，当 i 到达最后索引时，停止
     * 找到了 1 个美丽子集
     * 注意：1 <= nums[i], k <= 1000 数据范围较小，可以用
     * 数组统计之前选择的数字数量
     */
    public int beautifulSubsets(int[] nums, int k) {

        dfs(0, nums, k, new int[10001 + k]);

        return cnt - 1;
    }

    private int cnt = 0;

    private void dfs(int i, int[] nums, int k, int[] record) {
        if (i == nums.length) {
            cnt++;
            return;
        }

        dfs(i + 1, nums, k, record);
        if (record[nums[i] + k] <= 0 && (
                nums[i] - k < 0 ||
                        record[nums[i] - k] <= 0)) {
            record[nums[i]]++;
            dfs(i + 1, nums, k, record);
            // 需要恢复现场
            record[nums[i]]--;
        }
    }

}
